package com.future;

/**
 * Description: 208. ʵ�� Trie (ǰ׺��)
 * ���������� "try"������˵ ǰ׺�� ��һ���������ݽṹ�����ڸ�Ч�ش洢�ͼ����ַ������ݼ��еļ�����һ���ݽṹ���൱���Ӧ���龰�������Զ������ƴд��顣
 * <p>
 * ����ʵ�� Trie �ࣺ
 * <p>
 * Trie() ��ʼ��ǰ׺������
 * void insert(String word) ��ǰ׺���в����ַ��� word ��
 * boolean search(String word) ����ַ��� word ��ǰ׺���У����� true�������ڼ���֮ǰ�Ѿ����룩�����򣬷��� false ��
 * boolean startsWith(String prefix) ���֮ǰ�Ѿ�������ַ���?word ��ǰ׺֮һΪ prefix ������ true �����򣬷��� false ��
 * <p>
 * ʾ����
 * <p>
 * ����
 * ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
 * [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
 * ���
 * [null, null, true, false, true, null, true]
 * <p>
 * ����
 * Trie trie = new Trie();
 * trie.insert("apple");
 * trie.search("apple");   // ���� True
 * trie.search("app");     // ���� False
 * trie.startsWith("app"); // ���� True
 * trie.insert("app");
 * trie.search("app");     // ���� True
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/implement-trie-prefix-tree
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/4/29 14:19
 */
public class Solution_208 {

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));// ���� True
        System.out.println(trie.search("app")); // ���� False
        System.out.println(trie.startsWith("app"));// ���� True
        trie.insert("app");
        System.out.println(trie.search("app"));// ���� True
    }

    private static class Trie {

        private Node root;

        public Trie() {
            root = new Node();
        }

        public void insert(String word) {
            if (word == null || word.length() == 0) {
                return;
            }
            Node curNode = root;
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                int path = chars[i] - 'a';
                Node next = curNode.nexts[path];
                if (next == null) {
                    next = new Node(path);
                }
                curNode.nexts[path] = next;
                curNode = next;
            }
            curNode.end++;
        }

        public boolean search(String word) {
            if (word == null || word.length() == 0) {
                return false;
            }
            Node curNode = root;
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                int path = chars[i] - 'a';
                Node next = curNode.nexts[path];
                if (next == null) {
                    return false;
                }
                curNode = next;
            }
            if (curNode.end > 0) {
                return true;
            }
            return false;
        }

        public boolean startsWith(String prefix) {
            if (prefix == null || prefix.length() == 0) {
                return false;
            }
            Node curNode = root;
            char[] chars = prefix.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                int path = chars[i] - 'a';
                Node next = curNode.nexts[path];
                if (next == null) {
                    return false;
                }
                curNode = next;
            }
            return true;
        }
    }

    private static class Node {
        public int aChar;
        public int end; // ����Ƿ����и��ַ�������ڵ�Ϊĩβ
        public Node[] nexts = new Node[26];

        public Node(int aChar) {
            this.aChar = aChar;
        }

        public Node() {

        }
    }
}
